package name.huzhenbo.java.algorithm.graph;

import name.huzhenbo.java.collection.Queue;

class Traverser {
    public static void dfs(Graph graph) {
        int[] visited = new int[graph.vertexNum()];

        for (int i = 0; i < graph.vertexNum(); i++) {
            if (visited[i] == 0) {
                _dfs(graph, i, visited);
            }
        }

    }

    private static void _dfs(Graph graph, int i, int[] visited) {
        visit(visited, i);
        for (int w = graph.firstAdjVex(i); w >= 0; w = graph.nextAdjVex(i, w)) {
            if (visited[w] == 0) {
                _dfs(graph, w, visited);
            }
        }
    }

    public static void bfs(Graph graph) {
        int[] visited = new int[graph.vertexNum()];

        for (int i = 0; i < graph.vertexNum(); i++) {
            if (visited[i] == 0) {
                Queue<Integer> queue = new Queue<Integer>();
                visit(visited, i);
                queue.en(i);
                while (!queue.isEmpty()) {
                    int j = queue.de();
                    for (int w = graph.firstAdjVex(j); w >= 0; w = graph.nextAdjVex(j, w)) {
                        if (visited[w] == 0) {
                            visit(visited, w);
                            queue.en(w);
                        }
                    }
                }
            }
        }
    }


    private static void visit(int[] visited, int i) {
        visited[i] = 1;
        System.out.println(i);
    }
}
